package test2;

import java.util.*;

public class ProcessScheduling {

    // FCFS调度算法
    public static void fcfsScheduling(List<Process> processes) {
        System.out.println("\nFCFS调度算法");

        // 按到达时间排序
        processes.sort((p1, p2) -> {
            if (p1.arrivalTime != p2.arrivalTime) {
                return Integer.compare(p1.arrivalTime, p2.arrivalTime);
            }
            return Integer.compare(p1.pid, p2.pid);
        });

        int currentTime = 0;
        List<Integer> scheduleOrder = new ArrayList<>();

        for (Process p : processes) {
            if (currentTime < p.arrivalTime) {
                currentTime = p.arrivalTime;
            }

            p.startTime = currentTime;
            p.completionTime = currentTime + p.burstTime;
            p.turnaroundTime = p.completionTime - p.arrivalTime;
            p.waitingTime = p.turnaroundTime - p.burstTime;
            p.responseTime = p.startTime - p.arrivalTime;

            scheduleOrder.add(p.pid);
            currentTime = p.completionTime;
        }

        // 输出调度顺序
        System.out.print("调度顺序: ");
        for (int pid : scheduleOrder) {
            System.out.print("P" + pid + " ");
        }

        // 输出进程详细信息
        printProcessDetails(processes);
        printPerformanceMetrics(processes);
    }

    // SJF调度算法（非抢占式）
    public static void sjfScheduling(List<Process> processes) {
        System.out.println("\nSJF调度算法（非抢占式）");

        int n = processes.size();
        int completed = 0;
        int currentTime = 0;
        List<Integer> scheduleOrder = new ArrayList<>();

        // 重置进程状态
        for (Process p : processes) {
            p.isCompleted = false;
            p.startTime = -1;
        }

        while (completed < n) {
            Process selected = null;
            int minBurstTime = Integer.MAX_VALUE;

            // 查找当前可执行且运行时间最短的进程
            for (Process p : processes) {
                if (!p.isCompleted && p.arrivalTime <= currentTime) {
                    if (p.burstTime < minBurstTime) {
                        minBurstTime = p.burstTime;
                        selected = p;
                    } else if (p.burstTime == minBurstTime) {
                        if (selected == null || p.arrivalTime < selected.arrivalTime) {
                            selected = p;
                        } else if (p.arrivalTime == selected.arrivalTime && p.pid < selected.pid) {
                            selected = p;
                        }
                    }
                }
            }

            if (selected != null) {
                selected.startTime = currentTime;
                selected.completionTime = currentTime + selected.burstTime;
                selected.turnaroundTime = selected.completionTime - selected.arrivalTime;
                selected.waitingTime = selected.turnaroundTime - selected.burstTime;
                selected.responseTime = selected.startTime - selected.arrivalTime;
                selected.isCompleted = true;

                scheduleOrder.add(selected.pid);
                currentTime = selected.completionTime;
                completed++;
            } else {
                // 没有进程到达，时间前进
                currentTime++;
            }
        }

        // 输出调度顺序
        System.out.print("调度顺序: ");
        for (int pid : scheduleOrder) {
            System.out.print("P" + pid + " ");
        }

        // 输出进程详细信息
        printProcessDetails(processes);
        printPerformanceMetrics(processes);
    }

    // RR调度算法
    public static void rrScheduling(List<Process> processes, int timeQuantum) {
        System.out.println("\nRR调度算法(时间片=" + timeQuantum + ")");

        int n = processes.size();
        int completed = 0;
        int currentTime = 0;
        Queue<Process> readyQueue = new LinkedList<>();
        List<Integer> scheduleOrder = new ArrayList<>();

        // 重置进程状态
        for (Process p : processes) {
            p.remainingTime = p.burstTime;
            p.isCompleted = false;
            p.isInQueue = false;
            p.startTime = -1;
        }

        // 初始到达的进程加入队列
        for (Process p : processes) {
            if (p.arrivalTime <= currentTime && !p.isInQueue) {
                readyQueue.add(p);
                p.isInQueue = true;
            }
        }

        while (completed < n) {
            if (!readyQueue.isEmpty()) {
                Process currentProcess = readyQueue.poll();

                // 记录第一次开始执行的时间
                if (currentProcess.startTime == -1) {
                    currentProcess.startTime = currentTime;
                    currentProcess.responseTime = currentProcess.startTime - currentProcess.arrivalTime;
                }

                // 执行进程
                int executionTime = Math.min(currentProcess.remainingTime, timeQuantum);
                scheduleOrder.add(currentProcess.pid);

                currentTime += executionTime;
                currentProcess.remainingTime -= executionTime;

                // 检查新到达的进程
                for (Process p : processes) {
                    if (!p.isCompleted && !p.isInQueue && p.arrivalTime <= currentTime) {
                        readyQueue.add(p);
                        p.isInQueue = true;
                    }
                }

                // 处理当前进程
                if (currentProcess.remainingTime == 0) {
                    // 进程完成
                    currentProcess.completionTime = currentTime;
                    currentProcess.turnaroundTime = currentProcess.completionTime - currentProcess.arrivalTime;
                    currentProcess.waitingTime = currentProcess.turnaroundTime - currentProcess.burstTime;
                    currentProcess.isCompleted = true;
                    completed++;
                } else {
                    // 进程未完成，重新加入队列
                    readyQueue.add(currentProcess);
                }
            } else {
                // 队列为空，时间前进
                currentTime++;
                // 检查是否有新进程到达
                for (Process p : processes) {
                    if (!p.isCompleted && !p.isInQueue && p.arrivalTime <= currentTime) {
                        readyQueue.add(p);
                        p.isInQueue = true;
                    }
                }
            }
        }

        // 输出调度顺序
        System.out.print("调度顺序: ");
        for (int pid : scheduleOrder) {
            System.out.print("P" + pid + " ");
        }

        // 输出进程详细信息
        printProcessDetails(processes);
        printPerformanceMetrics(processes);
    }

    // 输出进程详细信息
    private static void printProcessDetails(List<Process> processes) {
        System.out.println("\n进程:");
        System.out.println("进程编号 到达时间 预计运行时间 开始执行时间 完成时间 周转时间 等待时间 响应时间");
        for (Process p : processes) {
            System.out.println(p);
        }
    }

    // 计算并输出性能指标
    private static void printPerformanceMetrics(List<Process> processes) {
        double avgTAT = 0, avgWT = 0, avgRT = 0;

        for (Process p : processes) {
            avgTAT += p.turnaroundTime;
            avgWT += p.waitingTime;
            avgRT += p.responseTime;
        }

        avgTAT /= processes.size();
        avgWT /= processes.size();
        avgRT /= processes.size();

        System.out.printf("平均周转时间=%.2f, 平均等待时间=%.2f, 平均响应时间=%.2f\n",
                avgTAT, avgWT, avgRT);
    }

    // 测试用例
    public static List<Process> createTestCase1() {
        // 常规场景：进程到达时间不同，运行时间长短不一
        List<Process> processes = new ArrayList<>();
        processes.add(new Process(1, 0, 10));
        processes.add(new Process(2, 2, 5));
        processes.add(new Process(3, 4, 3));
        processes.add(new Process(4, 6, 7));
        processes.add(new Process(5, 8, 2));
        return processes;
    }

    public static List<Process> createTestCase2() {
        // 短进程集中场景：大部分为短进程，少数为长进程
        List<Process> processes = new ArrayList<>();
        processes.add(new Process(1, 0, 1));
        processes.add(new Process(2, 1, 2));
        processes.add(new Process(3, 2, 1));
        processes.add(new Process(4, 3, 15)); // 长进程
        processes.add(new Process(5, 4, 3));
        processes.add(new Process(6, 5, 2));
        return processes;
    }

    public static List<Process> createTestCase3() {
        // 进程同时到达场景：所有进程同时到达
        List<Process> processes = new ArrayList<>();
        processes.add(new Process(1, 0, 8));
        processes.add(new Process(2, 0, 4));
        processes.add(new Process(3, 0, 12));
        processes.add(new Process(4, 0, 6));
        processes.add(new Process(5, 0, 3));
        return processes;
    }

    public static void main(String[] args) {
        // 测试三个测试用例
        List<List<Process>> testCases = new ArrayList<>();
        testCases.add(createTestCase1());
        testCases.add(createTestCase2());
        testCases.add(createTestCase3());

        String[] testCaseNames = {"测试用例1（常规场景）", "测试用例2（短进程集中）", "测试用例3（同时到达）"};

        for (int i = 0; i < testCases.size(); i++) {
            System.out.println();
            System.out.println(testCaseNames[i]);

            List<Process> processes = new ArrayList<>();
            for (Process p : testCases.get(i)) {
                processes.add(new Process(p.pid, p.arrivalTime, p.burstTime));
            }
            fcfsScheduling(processes);

            processes = new ArrayList<>();
            for (Process p : testCases.get(i)) {
                processes.add(new Process(p.pid, p.arrivalTime, p.burstTime));
            }
            sjfScheduling(processes);

            processes = new ArrayList<>();
            for (Process p : testCases.get(i)) {
                processes.add(new Process(p.pid, p.arrivalTime, p.burstTime));
            }
            rrScheduling(processes, 4); // 时间片设为4
        }
    }
}
